// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/schedule.h"

#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"
#include "src/ostreams.h"

namespace v8 {
namespace internal {
    namespace compiler {

        BasicBlock::BasicBlock(Zone* zone, Id id)
            : loop_number_(-1)
            , rpo_number_(-1)
            , deferred_(false)
            , dominator_depth_(-1)
            , dominator_(nullptr)
            , rpo_next_(nullptr)
            , loop_header_(nullptr)
            , loop_end_(nullptr)
            , loop_depth_(0)
            , control_(kNone)
            , control_input_(nullptr)
            , nodes_(zone)
            , successors_(zone)
            , predecessors_(zone)
            ,
#if DEBUG
            debug_info_(AssemblerDebugInfo(nullptr, nullptr, -1))
            ,
#endif
            id_(id)
        {
        }

        bool BasicBlock::LoopContains(BasicBlock* block) const
        {
            // RPO numbers must be initialized.
            DCHECK_LE(0, rpo_number_);
            DCHECK_LE(0, block->rpo_number_);
            if (loop_end_ == nullptr)
                return false; // This is not a loop.
            return block->rpo_number_ >= rpo_number_ && block->rpo_number_ < loop_end_->rpo_number_;
        }

        void BasicBlock::AddSuccessor(BasicBlock* successor)
        {
            successors_.push_back(successor);
        }

        void BasicBlock::AddPredecessor(BasicBlock* predecessor)
        {
            predecessors_.push_back(predecessor);
        }

        void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }

        void BasicBlock::set_control(Control control) { control_ = control; }

        void BasicBlock::set_control_input(Node* control_input)
        {
            if (!nodes_.empty() && control_input == nodes_.back()) {
                nodes_.pop_back();
            }
            control_input_ = control_input;
        }

        void BasicBlock::set_loop_depth(int32_t loop_depth)
        {
            loop_depth_ = loop_depth;
        }

        void BasicBlock::set_rpo_number(int32_t rpo_number)
        {
            rpo_number_ = rpo_number;
        }

        void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }

        void BasicBlock::set_loop_header(BasicBlock* loop_header)
        {
            loop_header_ = loop_header;
        }

        // static
        BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2)
        {
            while (b1 != b2) {
                if (b1->dominator_depth() < b2->dominator_depth()) {
                    b2 = b2->dominator();
                } else {
                    b1 = b1->dominator();
                }
            }
            return b1;
        }

        void BasicBlock::Print() { StdoutStream {} << this; }

        std::ostream& operator<<(std::ostream& os, const BasicBlock& block)
        {
            os << "B" << block.id();
#if DEBUG
            AssemblerDebugInfo info = block.debug_info();
            if (info.name)
                os << info;
            // Print predecessor blocks for better debugging.
            const int kMaxDisplayedBlocks = 4;
            int i = 0;
            const BasicBlock* current_block = &block;
            while (current_block->PredecessorCount() > 0 && i++ < kMaxDisplayedBlocks) {
                current_block = current_block->predecessors().front();
                os << " <= B" << current_block->id();
                info = current_block->debug_info();
                if (info.name)
                    os << info;
            }
#endif
            return os;
        }

        std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c)
        {
            switch (c) {
            case BasicBlock::kNone:
                return os << "none";
            case BasicBlock::kGoto:
                return os << "goto";
            case BasicBlock::kCall:
                return os << "call";
            case BasicBlock::kBranch:
                return os << "branch";
            case BasicBlock::kSwitch:
                return os << "switch";
            case BasicBlock::kDeoptimize:
                return os << "deoptimize";
            case BasicBlock::kTailCall:
                return os << "tailcall";
            case BasicBlock::kReturn:
                return os << "return";
            case BasicBlock::kThrow:
                return os << "throw";
            }
            UNREACHABLE();
        }

        std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id)
        {
            return os << id.ToSize();
        }

        Schedule::Schedule(Zone* zone, size_t node_count_hint)
            : zone_(zone)
            , all_blocks_(zone)
            , nodeid_to_block_(zone)
            , rpo_order_(zone)
            , start_(NewBasicBlock())
            , end_(NewBasicBlock())
        {
            nodeid_to_block_.reserve(node_count_hint);
        }

        BasicBlock* Schedule::block(Node* node) const
        {
            if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
                return nodeid_to_block_[node->id()];
            }
            return nullptr;
        }

        bool Schedule::IsScheduled(Node* node)
        {
            if (node->id() >= nodeid_to_block_.size())
                return false;
            return nodeid_to_block_[node->id()] != nullptr;
        }

        BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id)
        {
            DCHECK(block_id.ToSize() < all_blocks_.size());
            return all_blocks_[block_id.ToSize()];
        }

        bool Schedule::SameBasicBlock(Node* a, Node* b) const
        {
            BasicBlock* block = this->block(a);
            return block != nullptr && block == this->block(b);
        }

        BasicBlock* Schedule::NewBasicBlock()
        {
            BasicBlock* block = new (zone_)
                BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
            all_blocks_.push_back(block);
            return block;
        }

        void Schedule::PlanNode(BasicBlock* block, Node* node)
        {
            if (FLAG_trace_turbo_scheduler) {
                StdoutStream {} << "Planning #" << node->id() << ":"
                                << node->op()->mnemonic() << " for future add to B"
                                << block->id() << "\n";
            }
            DCHECK_NULL(this->block(node));
            SetBlockForNode(block, node);
        }

        void Schedule::AddNode(BasicBlock* block, Node* node)
        {
            if (FLAG_trace_turbo_scheduler) {
                StdoutStream {} << "Adding #" << node->id() << ":" << node->op()->mnemonic()
                                << " to B" << block->id() << "\n";
            }
            DCHECK(this->block(node) == nullptr || this->block(node) == block);
            block->AddNode(node);
            SetBlockForNode(block, node);
        }

        void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ)
        {
            DCHECK_EQ(BasicBlock::kNone, block->control());
            block->set_control(BasicBlock::kGoto);
            AddSuccessor(block, succ);
        }

#if DEBUG
        namespace {

            bool IsPotentiallyThrowingCall(IrOpcode::Value opcode)
            {
                switch (opcode) {
#define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
                    JS_OP_LIST(BUILD_BLOCK_JS_CASE)
#undef BUILD_BLOCK_JS_CASE
                case IrOpcode::kCall:
                case IrOpcode::kCallWithCallerSavedRegisters:
                    return true;
                default:
                    return false;
                }
            }

        } // namespace
#endif // DEBUG

        void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
            BasicBlock* exception_block)
        {
            DCHECK_EQ(BasicBlock::kNone, block->control());
            DCHECK(IsPotentiallyThrowingCall(call->opcode()));
            block->set_control(BasicBlock::kCall);
            AddSuccessor(block, success_block);
            AddSuccessor(block, exception_block);
            SetControlInput(block, call);
        }

        void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
            BasicBlock* fblock)
        {
            DCHECK_EQ(BasicBlock::kNone, block->control());
            DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
            block->set_control(BasicBlock::kBranch);
            AddSuccessor(block, tblock);
            AddSuccessor(block, fblock);
            SetControlInput(block, branch);
        }

        void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
            size_t succ_count)
        {
            DCHECK_EQ(BasicBlock::kNone, block->control());
            DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
            block->set_control(BasicBlock::kSwitch);
            for (size_t index = 0; index < succ_count; ++index) {
                AddSuccessor(block, succ_blocks[index]);
            }
            SetControlInput(block, sw);
        }

        void Schedule::AddTailCall(BasicBlock* block, Node* input)
        {
            DCHECK_EQ(BasicBlock::kNone, block->control());
            block->set_control(BasicBlock::kTailCall);
            SetControlInput(block, input);
            if (block != end())
                AddSuccessor(block, end());
        }

        void Schedule::AddReturn(BasicBlock* block, Node* input)
        {
            DCHECK_EQ(BasicBlock::kNone, block->control());
            block->set_control(BasicBlock::kReturn);
            SetControlInput(block, input);
            if (block != end())
                AddSuccessor(block, end());
        }

        void Schedule::AddDeoptimize(BasicBlock* block, Node* input)
        {
            DCHECK_EQ(BasicBlock::kNone, block->control());
            block->set_control(BasicBlock::kDeoptimize);
            SetControlInput(block, input);
            if (block != end())
                AddSuccessor(block, end());
        }

        void Schedule::AddThrow(BasicBlock* block, Node* input)
        {
            DCHECK_EQ(BasicBlock::kNone, block->control());
            block->set_control(BasicBlock::kThrow);
            SetControlInput(block, input);
            if (block != end())
                AddSuccessor(block, end());
        }

        void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
            BasicBlock* tblock, BasicBlock* fblock)
        {
            DCHECK_NE(BasicBlock::kNone, block->control());
            DCHECK_EQ(BasicBlock::kNone, end->control());
            end->set_control(block->control());
            block->set_control(BasicBlock::kBranch);
            MoveSuccessors(block, end);
            AddSuccessor(block, tblock);
            AddSuccessor(block, fblock);
            if (block->control_input() != nullptr) {
                SetControlInput(end, block->control_input());
            }
            SetControlInput(block, branch);
        }

        void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
            BasicBlock** succ_blocks, size_t succ_count)
        {
            DCHECK_NE(BasicBlock::kNone, block->control());
            DCHECK_EQ(BasicBlock::kNone, end->control());
            end->set_control(block->control());
            block->set_control(BasicBlock::kSwitch);
            MoveSuccessors(block, end);
            for (size_t index = 0; index < succ_count; ++index) {
                AddSuccessor(block, succ_blocks[index]);
            }
            if (block->control_input() != nullptr) {
                SetControlInput(end, block->control_input());
            }
            SetControlInput(block, sw);
        }

        void Schedule::EnsureCFGWellFormedness()
        {
            // Make a copy of all the blocks for the iteration, since adding the split
            // edges will allocate new blocks.
            BasicBlockVector all_blocks_copy(all_blocks_);

            // Insert missing split edge blocks.
            for (BasicBlock* block : all_blocks_copy) {
                if (block->PredecessorCount() > 1) {
                    if (block != end_) {
                        EnsureSplitEdgeForm(block);
                    }
                    if (block->deferred()) {
                        EnsureDeferredCodeSingleEntryPoint(block);
                    }
                }
            }

            EliminateRedundantPhiNodes();
        }

        void Schedule::EliminateRedundantPhiNodes()
        {
            // Ensure that useless phi nodes that only have a single input, identical
            // inputs, or are a self-referential loop phi,
            // -- which can happen with the automatically generated code in the CSA and
            // torque -- are pruned.
            // Since we have strucured control flow, this is enough to minimize the number
            // of phi nodes.
            bool reached_fixed_point = false;
            while (!reached_fixed_point) {
                reached_fixed_point = true;
                for (BasicBlock* block : all_blocks_) {
                    int predecessor_count = static_cast<int>(block->PredecessorCount());
                    for (size_t node_pos = 0; node_pos < block->NodeCount(); ++node_pos) {
                        Node* node = block->NodeAt(node_pos);
                        if (node->opcode() == IrOpcode::kPhi) {
                            Node* first_input = node->InputAt(0);
                            bool inputs_equal = true;
                            for (int i = 1; i < predecessor_count; ++i) {
                                Node* input = node->InputAt(i);
                                if (input != first_input && input != node) {
                                    inputs_equal = false;
                                    break;
                                }
                            }
                            if (!inputs_equal)
                                continue;
                            node->ReplaceUses(first_input);
                            block->RemoveNode(block->begin() + node_pos);
                            --node_pos;
                            reached_fixed_point = false;
                        }
                    }
                }
            }
        }

        void Schedule::EnsureSplitEdgeForm(BasicBlock* block)
        {
#ifdef DEBUG
            DCHECK(block->PredecessorCount() > 1 && block != end_);
            for (auto current_pred = block->predecessors().begin();
                 current_pred != block->predecessors().end(); ++current_pred) {
                BasicBlock* pred = *current_pred;
                DCHECK_LE(pred->SuccessorCount(), 1);
            }
#endif
        }

        void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block)
        {
            // If a deferred block has multiple predecessors, they have to
            // all be deferred. Otherwise, we can run into a situation where a range
            // that spills only in deferred blocks inserts its spill in the block, but
            // other ranges need moves inserted by ResolveControlFlow in the predecessors,
            // which may clobber the register of this range.
            // To ensure that, when a deferred block has multiple predecessors, and some
            // are not deferred, we add a non-deferred block to collect all such edges.

            DCHECK(block->deferred() && block->PredecessorCount() > 1);
            bool all_deferred = true;
            for (auto current_pred = block->predecessors().begin();
                 current_pred != block->predecessors().end(); ++current_pred) {
                BasicBlock* pred = *current_pred;
                if (!pred->deferred()) {
                    all_deferred = false;
                    break;
                }
            }

            if (all_deferred)
                return;
            BasicBlock* merger = NewBasicBlock();
            merger->set_control(BasicBlock::kGoto);
            merger->successors().push_back(block);
            for (auto current_pred = block->predecessors().begin();
                 current_pred != block->predecessors().end(); ++current_pred) {
                BasicBlock* pred = *current_pred;
                merger->predecessors().push_back(pred);
                pred->successors().clear();
                pred->successors().push_back(merger);
            }
            merger->set_deferred(false);
            block->predecessors().clear();
            block->predecessors().push_back(merger);
            MovePhis(block, merger);
        }

        void Schedule::MovePhis(BasicBlock* from, BasicBlock* to)
        {
            for (size_t i = 0; i < from->NodeCount();) {
                Node* node = from->NodeAt(i);
                if (node->opcode() == IrOpcode::kPhi) {
                    to->AddNode(node);
                    from->RemoveNode(from->begin() + i);
                    DCHECK_EQ(nodeid_to_block_[node->id()], from);
                    nodeid_to_block_[node->id()] = to;
                } else {
                    ++i;
                }
            }
        }

        void Schedule::PropagateDeferredMark()
        {
            // Push forward the deferred block marks through newly inserted blocks and
            // other improperly marked blocks until a fixed point is reached.
            // TODO(danno): optimize the propagation
            bool done = false;
            while (!done) {
                done = true;
                for (auto block : all_blocks_) {
                    if (!block->deferred()) {
                        bool deferred = block->PredecessorCount() > 0;
                        for (auto pred : block->predecessors()) {
                            if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
                                deferred = false;
                            }
                        }
                        if (deferred) {
                            block->set_deferred(true);
                            done = false;
                        }
                    }
                }
            }
        }

        void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ)
        {
            block->AddSuccessor(succ);
            succ->AddPredecessor(block);
        }

        void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to)
        {
            for (BasicBlock* const successor : from->successors()) {
                to->AddSuccessor(successor);
                for (BasicBlock*& predecessor : successor->predecessors()) {
                    if (predecessor == from)
                        predecessor = to;
                }
            }
            from->ClearSuccessors();
        }

        void Schedule::SetControlInput(BasicBlock* block, Node* node)
        {
            block->set_control_input(node);
            SetBlockForNode(block, node);
        }

        void Schedule::SetBlockForNode(BasicBlock* block, Node* node)
        {
            if (node->id() >= nodeid_to_block_.size()) {
                nodeid_to_block_.resize(node->id() + 1);
            }
            nodeid_to_block_[node->id()] = block;
        }

        std::ostream& operator<<(std::ostream& os, const Schedule& s)
        {
            for (BasicBlock* block :
                ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
                if (block->rpo_number() == -1) {
                    os << "--- BLOCK id:" << block->id().ToInt();
                } else {
                    os << "--- BLOCK B" << block->rpo_number();
                }
                if (block->deferred())
                    os << " (deferred)";
                if (block->PredecessorCount() != 0)
                    os << " <- ";
                bool comma = false;
                for (BasicBlock const* predecessor : block->predecessors()) {
                    if (comma)
                        os << ", ";
                    comma = true;
                    if (predecessor->rpo_number() == -1) {
                        os << "id:" << predecessor->id().ToInt();
                    } else {
                        os << "B" << predecessor->rpo_number();
                    }
                }
                os << " ---\n";
                for (Node* node : *block) {
                    os << "  " << *node;
                    if (NodeProperties::IsTyped(node)) {
                        os << " : " << NodeProperties::GetType(node);
                    }
                    os << "\n";
                }
                BasicBlock::Control control = block->control();
                if (control != BasicBlock::kNone) {
                    os << "  ";
                    if (block->control_input() != nullptr) {
                        os << *block->control_input();
                    } else {
                        os << "Goto";
                    }
                    os << " -> ";
                    comma = false;
                    for (BasicBlock const* successor : block->successors()) {
                        if (comma)
                            os << ", ";
                        comma = true;
                        if (successor->rpo_number() == -1) {
                            os << "id:" << successor->id().ToInt();
                        } else {
                            os << "B" << successor->rpo_number();
                        }
                    }
                    os << "\n";
                }
            }
            return os;
        }

    } // namespace compiler
} // namespace internal
} // namespace v8
